# -*- coding: utf-8 -*-
# Python中默认的编码格式是 ASCII 格式，在没修改编码格式时无法正确打印汉字，所以在读取中文时会报错。

# 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
#
# 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
# 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
#
# 进阶:
#
# 你是否可以在 O(1) 时间复杂度内完成这两种操作？
#
# 示例:
#
# LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
#
# cache.put(1, 1);
# cache.put(2, 2);
# cache.get(1);       // 返回  1
# cache.put(3, 3);    // 该操作会使得密钥 2 作废
# cache.get(2);       // 返回 -1 (未找到)
# cache.put(4, 4);    // 该操作会使得密钥 1 作废
# cache.get(1);       // 返回 -1 (未找到)
# cache.get(3);       // 返回  3
# cache.get(4);       // 返回  4
from collections import OrderedDict


# 自己 如果未使用，会作废掉最新的 不是很合理
class LRUCashe():
    def __init__(self, capacity):
        self.capacity = capacity
        self.value = {}
        self.count = 0
        self.lru = OrderedDict()

    def get(self, key):
        if key in self.value.keys():
            value = int(self.lru[key]) + 1
            self.lru[key] = value
            return self.value[key]
        if key not in self.value.keys():
            return -1

    def put(self, key, value):
        if self.count >= self.capacity:
            l = []
            for i in self.lru.values():
                l.append(i)
            mi = min(l)
            # print("mi" + str(mi))
            for i in self.lru.values():
                if mi == i:
                    new_dict = {v: k for k, v in self.lru.items()}
                    s = new_dict[mi]
                    print("s" + str(s))
                    del self.value[s]
                    del self.lru[s]
                    self.value[key] = value
                    self.lru[key] = 0
                    self.count += 1
                    break

        else:
            self.value[key] = value
            self.lru[key] = 0
            self.count += 1

# 答案
# 有一种叫做有序字典的数据结构，综合了哈希表和链表，在 Python 中为 OrderedDict，在 Java 中为 LinkedHashMap。

if __name__ == "__main__":
    lru = LRUCashe(3)
    lru.put(1, "12")
    lru.put(2, "23")
    lru.put(3, "34")
    print(lru.get(3))
    lru.put(4, "45")
    lru.put(5, "56")
    print(lru.get(2))
    print(lru.get(2))
    print(lru.get(3))
    print(lru.get(1))
    print(lru.lru)

    # student = {'小萌': '1001', '小智': '1002', '小强': '1003', '小明': '1004'}
    # print(list(student.keys())[list(student.values()).index('1004')])
